package com.itheima.algorithm.binarytree;

import com.itheima.algorithm.stack.LinkedListStack;

import java.util.LinkedList;

/**
 * @author: TylerZhong
 * @description: 二叉树最大深度 - 使用后续遍历（非递归）求解
 */
public class E05Leetcode104_2 {

    /**
     * 思路：
     *  1. 使用非递归后续遍历，栈的最大高度即为最大深度
     * @param node
     * @return
     */
    public int maxDepth(TreeNode node) {
        TreeNode curr = node;
        TreeNode pop = null;
        LinkedList<TreeNode> stack = new LinkedList<>();
        int max = 0; // 栈的最大高度
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                if (stack.size() >= max) {
                    max = stack.size();
                }
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                } else {
                    curr = peek.right;
                }
            }
        }
        return max;
    }

}
